package com.eatme.core.sort;

import com.eatme.core.array.ArrayGenerator;

public class ShellSortV3 {

    public ShellSortV3() {

    }

    public static <E extends Comparable<E>> void sort(E[] data) {
//        int h = data.length/2;
        int h = 1;
        // h< data.length h< data.length/2 h< data.length/3
        while (h< data.length)h = h*3 +1;
        // h 1,4,13,40 ...
        // 对data[h,n),进行插入排序
        while (h>=1) {
                for (int i = h; i <data.length ; i++) {
                    E t = data[i];
                    int j;
                    for (j = i; j -h>=0&&t.compareTo(data[j-h])<0; j-=h)
                        data[j] =data[j-h];
                    data[j] =t;
                }
            h/=2;
        }
    }

    public static void main(String[] args) {
        int n = 1000000;
        System.out.println("RandomArray");
        Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
        SortingHelper.sortTest("ShellSortV3",arr);
    }
}
